Caching of data is used in computer systems for reducing the time required to access the data. A data cache is a data repository which typically has a faster access time, but smaller capacity, than other repositories for the data. Therefore, when data in the cache data is accessed, it can be accessed more quickly than if the data were stored elsewhere. Otherwise, if the data is not in the cache, the data must be retrieved from another data repository, which typically takes longer.
During operation of a computing system that employs a data cache, when a request for data is received, if the data is located in the cache, this is referred to as a “cache hit.” On the other hand, if the requested data is not located in the cache, this is referred to as a “cache miss.” For data cache management, it is desired to maximize the cache hit rate.
There exists a spectrum of schemes for populating and maintaining caches. These schemes generally he somewhere on a spectrum at one end of which is LRU (Least Recently Used) and other end of which is LFU (Least Frequently Used). LRU schemes emphasize recency; data items that have not been accessed recently are replaced in the cache with those that have been accessed recently. This is done with the expectation that an item that was accessed recently will be accessed again in the near future.
At the other end of the spectrum is LFU, which emphasizes frequency. LFU schemes cause data items which are accessed frequently to replace those items in the cache which have not been accessed frequently. This is done with the expectation that an item that was accessed frequently will be accessed again in the near future.
Other algorithms, such ARC (Adaptive Replacement Cache) and LRFU (Least Recently Frequently Used), attempt to capture benefits of both LRU and LFU policies.
While some cache management schemes are known, there is still room for improvement of such schemes. The present invention is directed to an improved technique for caching of data.
The present invention provides a system for and a method of data cache management. In accordance with an embodiment of the present invention, a method of cache management is provided. A request for access to data is received. A sample value is assigned to the request, the sample value being randomly selected according to a probability distribution. The sample value is compared to another value. The data is selectively stored in the cache based on results of the comparison.